Linear and mixed integer linear programming programs with optional quadratic or bilinear objective function terms generally involve seeking to solve for x.sub.i (i=1, . . . , n) so as to maximize the expression: ##EQU1## where the terms with a.sub.i coefficients are linear terms, and the terms with d.sub.ij coefficients are quadratic (bilinear) terms, when i equals (does not equal) j. This expression is referred to as the "objective function." Maximization of the objective function is generally subject to a set of constraints, of the form: ##EQU2## where each x.sub.i is a non-negative integer or real variable. If some subset of the x.sub.i are constrained by the nature of the problem to assume only discrete values, the computational complexity of the problem is compounded and the solution requires integer or mixed integer techniques.
An extensive literature is concerned with network optimization and linear programming, in particular, with algorithmic theory and computational efficiency. Much of the literature also deals with the identification of specific network and linear program problem types that admit of solution by means of specialized algorithms which are computationally more tractable than the general cases. The extraction of specialized structures or substructures from given network and linear program problems is also known in the art.
It is known in the prior art to use computers to solve network programs, linear programs, integer programs, mixed integer linear programs and mixed integer linear programs with quadratic or bilinear terms in the objective function (hereinafter collectively referred to as MILPQs). Commercial software packages, such as OSL and MPSX (from International Business Machines Corporation, Armonk, N.Y.), LINDO (from Lindo Systems, Chicago, Ill.), or CPLEX (from CPLEX Optimization Corp., Incline Village, Nev.), exist to solve such problems. Versions of these solvers frequently have the ability to identify and extract network and other problem structures and apply special, computationally more efficient network and linear programming algorithms in solving such problems. Nevertheless, in addressing real-world problems that may be characterized as MILPQs, it is typically difficult to set up the equations (such as those described above), because it is typically difficult to develop a manner of understanding such problems in such a way as to permit the equations to be easily written. Moreover, equations defining a MILPQ are not themselves easily understood or envisioned and may be extremely voluminous.
In addition to their computational efficiency aspects, network optimization techniques have representational aspects which include pictorial presentation of problem elements in terms of diagrams consisting of points or nodes joined by lines or links. This visual representation of a problem can greatly enhance understanding. Existing network solution software typically embeds all constraints on flows in the network node and link elements. Thus, where flows are absent in the real-world context, they may have to be created for the software to represent necessary problem constraints. A pertinent example considers N nodes connected to a node P with limited capacity, and this node connected, in turn, to M nodes, as depicted in FIG. 17. This example might represent a pipeline with multiple inputs and outputs at an interconnect, or a warehouse, etc. Suppose the problem requires constraints on every possible combination of inflows to P and outflows from P. The number of possible inflow constraints is 2.sup.N -1 (neglecting the null constraint), while the number of possible outflow constraints is 2.sup.M -1. If, as with conventional networks, the constraints have to be represented in the nodes and the links of the graph and each constraint can be represented, at the least, with a link (though more complex constraints arise frequently in real optimization problems), the number of dummy links that have to be created to represent the problem is at least (2.sup.N -1)*(2.sup.M -1). This exponential explosion in graph links would destroy the visual advantage of the pictorial representation by rendering the graph unreadable, the original graph topology unrecognizable, and the entire problem formulation suspect to all except its creator, thus, calling into question the utility of the tool.
It must be emphasized that constraints which arise in the majority of real-world network and linear programming problems entail complex relationships interrelating aspects of the problem. Relationships such as proportionality of one set of node or link flows with respect to combinations of flows other sets of nodes, links, or groups, as well as conditional dependencies among elements and groups of elements which are not otherwise related, are not easily represented using existing network techniques, if at all.